package com.shm.leetcode;

import java.util.Stack;

/**
 * 92. 反转链表 II
 * 给你单链表的头节点 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4,5], left = 2, right = 4
 * 输出：[1,4,3,2,5]
 * 示例 2：
 *
 * 输入：head = [5], left = 1, right = 1
 * 输出：[5]
 *
 *
 * 提示：
 *
 * 链表中节点数目为 n
 * 1 <= n <= 500
 * -500 <= Node.val <= 500
 * 1 <= left <= right <= n
 *
 *
 * 进阶： 你可以使用一趟扫描完成反转吗？
 * @author SHM
 */
public class ReverseBetween {
    /**
     * 方法二：一次遍历「穿针引线」反转链表
     * 方法一的缺点是：如果 left 和 right 的区域很大，恰好是链表的头节点和尾节点时，找到 left 和 right 需要遍历一次，反转它们之间的链表还需要遍历一次，虽然总的时间复杂度为 O(N)O(N)，但遍历了链表 22 次，可不可以只遍历一次呢？答案是可以的。我们依然画图进行说明。
     *
     * 我们依然以方法一的示例为例进行说明。
     *
     *
     *
     * 整体思想是：在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。下面的图展示了整个流程。
     *
     *
     *
     * 下面我们具体解释如何实现。使用三个指针变量 pre、curr、next 来记录反转的过程中需要的变量，它们的意义如下：
     *
     * curr：指向待反转区域的第一个节点 left；
     * next：永远指向 curr 的下一个节点，循环过程中，curr 变化以后 next 会变化；
     * pre：永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变。
     * 第 1 步，我们使用 ①、②、③ 标注「穿针引线」的步骤。
     *
     *
     *
     * 操作步骤：
     *
     * 先将 curr 的下一个节点记录为 next；
     * 执行操作 ①：把 curr 的下一个节点指向 next 的下一个节点；
     * 执行操作 ②：把 next 的下一个节点指向 pre 的下一个节点；
     * 执行操作 ③：把 pre 的下一个节点指向 next。
     * 第 1 步完成以后「拉直」的效果如下：
     *
     *
     *
     * 第 2 步，同理。同样需要注意 「穿针引线」操作的先后顺序。
     *
     *
     *
     * 第 2 步完成以后「拉直」的效果如下：
     *
     *
     *
     * 第 3 步，同理。
     *
     *
     *
     * 第 3 步完成以后「拉直」的效果如下：
     * 复杂度分析：
     *
     * 时间复杂度：O(N)O(N)，其中 NN 是链表总节点数。最多只遍历了链表一次，就完成了反转。
     *
     * 空间复杂度：O(1)O(1)。只使用到常数个变量。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/fan-zhuan-lian-biao-ii-by-leetcode-solut-teyq/
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dump = new ListNode(-1);
        dump.next = head;
        ListNode pre = dump;
        for(int i=0;i<left-1;i++){
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next;
        for(int i=0;i<right-left;i++){
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dump.next;
    }

    /**
     * 前言
     * 链表的操作问题，一般而言面试（机试）的时候不允许我们修改节点的值，而只能修改节点的指向操作。
     *
     * 思路通常都不难，写对链表问题的技巧是：一定要先想清楚思路，并且必要的时候在草稿纸上画图，理清「穿针引线」的先后步骤，然后再编码。
     *
     * 方法一：穿针引线
     * 我们以下图中黄色区域的链表反转为例。
     *
     *
     *
     * 使用「206. 反转链表」的解法，反转 left 到 right 部分以后，再拼接起来。我们还需要记录 left 的前一个节点，和 right 的后一个节点。如图所示：
     *
     *
     *
     * 算法步骤：
     *
     * 第 1 步：先将待反转的区域反转；
     * 第 2 步：把 pre 的 next 指针指向反转以后的链表头节点，把反转以后的链表的尾节点的 next 指针指向 succ。
     *
     *
     * 说明：编码细节我们不在题解中介绍了，请见下方代码。思路想明白以后，编码不是一件很难的事情。这里要提醒大家的是，链接什么时候切断，什么时候补上去，先后顺序一定要想清楚，如果想不清楚，可以在纸上模拟，让思路清晰。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(N)O(N)，其中 NN 是链表总节点数。最坏情况下，需要遍历整个链表。
     *
     * 空间复杂度：O(1)O(1)。只使用到常数个变量。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/fan-zhuan-lian-biao-ii-by-leetcode-solut-teyq/
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween_2(ListNode head, int left, int right) {
        ListNode dump = new ListNode(-1);
        dump.next = head;
        ListNode pre = dump;
        for(int i=0;i<left-1;i++){
            pre = pre.next;
        }
        ListNode rightNode = pre;
        for(int i=0;i<right-left+1;i++){
            rightNode = rightNode.next;
        }
        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;
        pre.next = null;
        rightNode.next = null;
        reverse(leftNode);

        pre.next = rightNode;
        leftNode.next = curr;
        return dump.next;
    }

    void reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur.next!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }

    public ListNode reverseBetween_3(ListNode head, int left, int right) {
        if (left==right||head==null){
            return head;
        }
        Stack<ListNode> stack = new Stack<>();
        int count =1;
        ListNode cur = head;
        ListNode start=null,end=null;
        while (cur!=null){
            if (count<left){
                start = cur;
            }else {
                if (count <= right) {
                    stack.push(cur);
                } else {
                    end = cur;
                    break;
                }
            }
            cur =cur.next;
            count++;
        }
        ListNode start1 = stack.peek();
        ListNode cur1 = stack.pop();
        while (!stack.isEmpty()){
            cur1.next = stack.peek();
            cur1 = stack.pop();
        }
        cur1.next = end;
        if (left==1){
            return start1;
        }
        start.next = start1;
        return head;
    }
}
